package nowcoder;
/**
 * -手套
 * 链接：https://www.nowcoder.com/practice/365d5722fff640a0b6684391153e58d8?tpId=49&&tqId=29337&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
 */
import java.util.ArrayList;

/**
 * 在地下里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手套个数不-定相同。
 * A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色,只能分辨出左右手。
 * 所以他会多拿手套，然后选出一双颜色相同的左右手套。现在的问题是，他至少要拿多少只手套(左手加右手)，
 * 才能保证一定能选出一双颜色相同的手套。
 * 给定颜色种数n(1<=n<=13)，同时给定两个长度为n的数组left,right,分别代表每种颜色左右手套的数量。
 * 数据保证左右的手套总数均不超过26,且-定存在至少一种合法方案。
 *
 * 输入：4, [0, 7, 1, 6], [1, 5, 0, 6]
 * 输出：10 (左手手套取2只，右手手套取8只)
 */
import java.util.*;
public class Day15_2 {
    public static void main(String[] args) {
        int n = 4;
        int[] left = {0, 7, 1, 6};
        int[] right = {1, 5, 0, 6};
        // 1 + 1 + 1 + 7
        System.out.println(findMinimum(n, left, right));
    }
    public static int findMinimum(int n, int[] left, int[] right) {
        // 好像是考虑最坏的情况
        int count = 0;
        //这两个链表存放可以凑出的左右手套的颜色
        List<Integer> isLeft = new ArrayList<>();
        List<Integer> isRight = new ArrayList<>();

        //如果有凑不出的颜色，就直接累加。因为情况最坏的话，你会取到凑不出的颜色
        for (int i = 0; i < left.length; i++) {
            //先看左手套为0的
            if(left[i] == 0){
                count += right[i];
            }
            //再看右手套为0的
            if(right[i] == 0){
                count += left[i];
            }
            //查完整手套
            if(left[i] != 0 && right[i] != 0){
                isLeft.add(left[i]);
                isRight.add(right[i]);
            }
        }

        //将可以凑出的颜色进行排序
        isLeft.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        isRight.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        //如果你想确保每种颜色都取到的话，就将它们全部取出来（除了数量最少的那个，只需取1个就行）
        int leftSum = 1, rightSum = 1;
        for (int i = 1; i < isLeft.size(); i++) {
            leftSum += isLeft.get(i);
            rightSum += isRight.get(i);
        }

        // 你只需要取一个一定能配套的左手或右手的手套就行
        count += 1;
        // 再配另一只手套，所以就看到底是配左手容易，还是配右手容易
        count += Math.min(leftSum, rightSum);
        return count;
    }
}
